package leetcode;

import java.util.HashSet;
import java.util.Set;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2022-01-02 19:36
 **/
public class LeetCode390 {

    public int lastRemaining(int n) {
        //left: 是否从左边移除
        boolean left = true;
        //step: 步数
        int step = 1;
        //head: 表示最左边剩余的节点
        int head = 1;

        //循环当元素个数大于1时
        while (n > 1) {
            //当从左边移除元素或者从右边移除元素且元素个数为奇数时,需要更新头结点
            if (left || (n & 1) == 1) {
                head += step;
            }

            //更新step
            step <<= 1;

            //移除一半的元素
            n >>= 1;

            //left取反,因为从左边移除元素后下一轮从右边移除
            left = !left;
        }

        return head;
    }

}
